/**************************************************************
          File Name:heap_sort.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: 2015-04-13 21:31:09
***************************************************************/

#include<stdio.h>
#include<stdlib.h>

#define l_child(idx)    (idx * 2 + 1) /* what if array start by 0 */
#define r_child(idx)    (idx * 2 + 2) /* what if array start by 0 */

static int my_size;
/*
int l_child(int idx)
{
    return idx*2;       // may fail when idx = 0
}

int r_child(int idx)
{
    return idx*2 + 1;   // may fail when idx = 0
}
*/
void to_heap(int A[], int n)
{
    int lc, rc, largest, tmp;

    for(;;)
    {
        lc = l_child(n);
        rc = r_child(n);

        if(lc <= my_size && A[lc] > A[n]) 
            largest = lc;
        else
            largest = n;
        if(rc <= my_size && A[rc] > A[largest])
            largest = rc;
        if(largest == n)
            break;
        
        tmp = A[n];
        A[n] = A[largest];
        A[largest] = tmp;
        to_heap(A, largest);
    }
}

void make_heap(int A[])
{
    int i;
    for(i = my_size / 2; i >= 0; i--)
        to_heap(A, i);
}

void heap_sort(int A[])
{
    int i, tmp;

    make_heap(A);

    for(i = my_size; i >= 1; i--)
    {
        tmp = A[0];
        A[0] = A[i];
        A[i] = tmp;
        my_size -= 1;
        to_heap(A, 0);
    }
}

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        fprintf(stderr, "%s length(how many elements in array to create)\n", argv[0]);
        exit(1);
    }

    my_size = atoi(argv[1]);
    int A[my_size], i, length;
    length = my_size;

    for(i = 0; i < my_size; i++)
        A[i] = rand();

    heap_sort(A);

    for(i=0; i< length; i++)
        printf("%d ", A[i]);
    putchar('\n');

    return 0;
}
